home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / falcon / programm.ing / nt_dsp1.lzh / NT_DSP1.MSA / SORT / SORT2.HLP < prev    next >
Text File  |  1989-01-24  |  2KB  |  51 lines
  1.          Name: SORT2
  2.          Type: Assembler Macro
  3.       Version: 1.1
  4.  Date Entered: 16-Sept-87
  5.   Last Change: 24-Sept-87 (improved speed)
  6.  
  7.   Description: Sorting an Array by Heapsort Method
  8.  
  9.  SORT2 is a programming example of the Heapsort method on the DSP56001.
  10.  The macro will sort an array of size "N_ITEMS" in X memory space
  11.  starting at location "ARRAY". 
  12.  
  13.  SORT2 uses the Heapsort method to sort an ARRAY of signed numbers. 
  14.  The sort is performed "in-place" and requires no additional memory
  15.  locations. The algorithm was invented by J. Williams [1] and is based
  16.  on a binary tree sort method.  It requires more complicated coding
  17.  but requires fewer elementary operations than more straightforward
  18.  methods [2]. 
  19.  
  20.  For SORT2 the execution time is proportional to NlogN, where N is
  21.  the array size (N_ITEMS).  Unlike SORT1, the execution time for
  22.  SORT2 is not constant for any given array size.  If the array is
  23.  already ordered, inversely ordered or randomly ordered, the execution
  24.  time will vary. The benchmarks are for randomly ordered arrays.
  25.  
  26.  SORT2 is more efficient for larger arrays.  The SORT1 macro is
  27.  efficient for sorting smaller arrays of numbers. 
  28.          
  29.  Benchmark Performances for 20.5MHz DSP56001:
  30.  
  31.  Array Size             SORT1                   SORT2
  32.  (N_ITEMS)      (Straight Selection)         (Heapsort)
  33.  ----------     --------------------         ----------
  34.       8                 14.5us                  51.7us
  35.      16                 41.8us                  130us
  36.      32                 134us                   317us
  37.      64                 468us                   741us
  38.     128                 1.7ms                   1.7ms
  39.     256                 6.7ms                   4.0ms
  40.     512                26.1ms                   9.1ms
  41.  
  42.  References
  43.  ----------
  44.  [1] Williams, J. W. J., "Heapsort" (Algorithm 232), Comm. ACM, 7, No. 6
  45.  (1964), 347-348.
  46.  
  47.  [2] Niklaus Wirth, "Algorithms + Data Structures = Programs,"
  48.  Prentice-Hall, 1976. pp. 70-76, Program 2.8.
  49.  
  50.  
  51.